
module Euler where

import Char
import Numeric
import Data.List
import Data.Maybe
import qualified Data.Map as Map

-----------------------------------------------------------------------------
-- #1
-- Add all the natural numbers below 1000 that are multiples of 3 or 5.

euler_p1 = sum [ x | x <- [1..999], x `mod` 3 == 0 || x `mod` 5 == 0]

-----------------------------------------------------------------------------
-- #2
-- Find the sum of all the even-valued terms in the Fibonacci sequence 
-- which do not exceed one million.

fib = [1,1] ++ [x+y | (x,y) <- zip fib (tail fib)]

-- haha, I rewrote takeWhile!
--take_while (x:xs) cond
--    | cond x = x : takeWhile xs cond 
--    | otherwise = []

euler_p2 = sum [ x | x <- takeWhile (<1000000) fib, x `mod` 2 == 0]

-----------------------------------------------------------------------------
-- #3
-- Find the largest prime factor of 317584931803.

-- This is a rewrite that is just as slow as my original lazy sequence one.
primeSieve [] = []
primeSieve (next:searchspace) = 
    next : primeSieve (filter (\x -> (x `mod` next) /= 0) searchspace)

-- A brute-force factor search
getSmallestFactor n = 
    let
        sqrt' = truncate $ sqrt $ fromIntegral n
        test [] = n
        test (x:xs) =
            if mod n x == 0
            then x
            else test xs
    in
        test [2..sqrt']

isPrime n = getSmallestFactor n == n

-- Successive factorization of integers
factor n = 
    let 
        gsf = getSmallestFactor n
    in
        if gsf == n
        then [gsf]
        else gsf : factor (truncate $ fromIntegral n / fromIntegral gsf)

isSquare x = x `mod` truncate (sqrt $ fromIntegral x) == 0

findCongruentSquares n limit 
    | n >= limit = (0,0)
    | otherwise =
        let modLimit = n^2 `mod` limit
        in
            if isSquare modLimit
            then 
                (n, truncate $ sqrt $ fromIntegral modLimit)
            else 
                findCongruentSquares (n+1) limit

getFactors start limit =
    let
        (x,y) = findCongruentSquares start limit
    in
        factor (gcd (x-y) limit) ++ factor (gcd (x+y) limit)

euler_p3 = 
    -- Use Fermat's factorization and hope for the best.
    -- (I looked it up on Wikipedia...)
    let
        magic = 317584931803
        sqrt' = truncate $ sqrt $ fromIntegral 317584931803
    in getFactors sqrt' magic

-----------------------------------------------------------------------------
-- #4
-- Find the largest palindrome made from the product of two 3-digit numbers.

paliSplit l =
    let
        (left,right) = splitAt ((length l) `quot` 2) l
    in
        if ((length l) `mod` 2) == 0
        then (left,right)
        else (left,tail right)

isPali n =
    let (left,right) = paliSplit $ show n
    in left == (reverse right)

isValidProduct :: Int -> Int -> (Bool,Int)
isValidProduct n m 
    | m < 100 = (False, 0)
    | m > 999 = (False, 0)
    | otherwise =
        if ((n `mod` m) == 0) && ((n `quot` m) > 100) && ((n `quot` m) < 1000)
        then (True, m)
        else isValidProduct n (m-1)
    
paliFinder :: Int -> (Int,(Int,Int))
paliFinder n
    | isPali n =
        let (isMatch,m) = isValidProduct n 999
        in
            if isMatch
            then (n,(quot n m, m))
            else paliFinder (n-1)
    | otherwise = paliFinder (n-1)       

euler_p4 = paliFinder 999999

-----------------------------------------------------------------------------
-- #5
-- What is the smallest number that is evenly divisible 
-- by all of the numbers from 1 to 20?
-- Strategy: start with primes, and tweak it from there

findCommon n [] = n
findCommon n (x:xs) =
    if (n `mod` x) == 0
    then findCommon n xs
    else findCommon (n*x) xs

reduceCommon :: Int -> [Int] -> [Int] -> Int
reduceCommon n matchList [] = n
reduceCommon n matchList (x:xs) =
    if (n `mod` x) == 0 && 
        (foldr (&&) True [(n `quot` x) `mod` y == 0 | y <- matchList])
    then reduceCommon (quot n x) matchList matchList
    else reduceCommon n matchList xs

euler_p5 = 
    let searchRange = [2..20]
    in reduceCommon (findCommon 20 searchRange) searchRange searchRange

-----------------------------------------------------------------------------
-- #6
-- Find the difference between the sum of the squares 
-- of the first one hundred natural numbers and the square of the sum.

euler_p6 =
    abs $ (sum [x^2 | x <- [1..100]]) - ((sum [1..100])^2)

-----------------------------------------------------------------------------
-- #7
-- Calculate the 10001st prime number.

euler_p7 = head $ reverse $ take 10001 $ primeSieve [2..]

-----------------------------------------------------------------------------
-- #8
-- Greatest product of five consecutive digits in big number

euler_p8 =
    let bigMutha = "7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"
        slider (a:b:c:d:e:f:cdr) =
            (a*b*c*d*e) : slider (b:c:d:e:f:cdr)
        slider (a:b:c:d:e:[]) = [(a*b*c*d*e)]
    in
        maximum $ slider $ map digitToInt bigMutha
        
-----------------------------------------------------------------------------
-- #9
-- There exists exactly one Pythagorean triplet for which a + b + c = 1000.
-- Find the product abc.
-- Brute-forced it to death.

euler_p9 =
    let
        permutations :: [Int] -> [[Int]] -> [[Int]]
        permutations [] b = []
        permutations a b = 
            [(head a):x | x <- b] ++
                permutations (tail a) b
        sqrtInt = truncate.sqrt.fromIntegral
        screenTriangles ((a2:b2:c2:[]):rest) 
            | ((a2+b2) == c2) =
                (map sqrtInt [a2,b2,c2]) : screenTriangles rest 
            | otherwise =
                screenTriangles rest
        screenTriangles [] = []
        
        squares = map (\x -> x*x) [1..1000]
    in
        foldr (*) 1 $
            head $ 
            filter (\x -> (foldr (+) 0 x) == 1000) $
            screenTriangles $
            permutations squares $
                permutations squares [[x] | x <- squares]
    
-----------------------------------------------------------------------------
-- #10
-- Calculate the sum of all the primes below one million.

euler_p10 = sum $ primeSieve [2..999999]

-----------------------------------------------------------------------------
-- #11
-- 
columns grid
    | grid == [] = []
    | head grid == [] = []
    | otherwise = 
        (map head grid) : (columns $ map tail grid)

diagonal grid
    | grid == [] = []
    | head grid == [] = []
    | otherwise = (head $ head grid) : (diagonal $ map tail $ tail grid)

halfMarch grid
    | grid == [] = []
    | head grid == [] = []
    | otherwise = 
        (diagonal grid) : 
        (halfMarch $ filter (\x -> x /= []) $ map tail grid)

diagMarch grid =
    (halfMarch grid) ++ (halfMarch $ map reverse $ reverse grid)

euler_p11 =
    let
        grid =
           [[08,02,22,97,38,15,00,40,00,75,04,05,07,78,52,12,50,77,91,08],
            [49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,04,56,62,00],
            [81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,03,49,13,36,65],
            [52,70,95,23,04,60,11,42,69,24,68,56,01,32,56,71,37,02,36,91],
            [22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80],
            [24,47,32,60,99,03,45,02,44,75,33,53,78,36,84,20,35,17,12,50],
            [32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70],
            [67,26,20,68,02,62,12,20,95,63,94,39,63,08,40,91,66,49,94,21],
            [24,55,58,05,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72],
            [21,36,23,09,75,00,76,44,20,45,35,14,00,61,33,97,34,31,33,95],
            [78,17,53,28,22,75,31,67,15,94,03,80,04,62,16,14,09,53,56,92],
            [16,39,05,42,96,35,31,47,55,58,88,24,00,17,54,24,36,29,85,57],
            [86,56,00,48,35,71,89,07,05,44,44,37,44,60,21,58,51,54,17,58],
            [19,80,81,68,05,94,47,69,28,73,92,13,86,52,17,77,04,89,55,40],
            [04,52,08,83,97,35,99,16,07,97,57,32,16,26,26,79,33,27,98,66],
            [88,36,68,87,57,62,20,72,03,46,33,67,46,55,12,32,63,93,53,69],
            [04,42,16,73,38,25,39,11,24,94,72,18,08,46,29,32,40,62,76,36],
            [20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,04,36,16],
            [20,73,35,29,78,31,90,01,74,31,49,71,48,86,81,16,23,57,05,54],
            [01,70,54,71,83,51,54,69,16,92,33,48,61,43,52,01,89,19,67,48]]
        slider (a:b:c:d:[]) = [a*b*c*d]
        slider (a:b:c:d:e:cdr) = 
            a*b*c*d : slider (b:c:d:e:cdr)
        slider l = []
        slideHoriz grid' = foldr (++) [] $ map slider grid'
        slideVert grid' = foldr (++) [] $ map slider $ columns grid'
        slideLeftDiag grid' = 
            foldr (++) [] $ map slider $ diagMarch grid'
        slideRightDiag grid' = 
            foldr (++) [] $ map slider $ diagMarch $ map reverse grid'
    in
        maximum $ slideHoriz grid ++ slideVert grid ++ 
            slideLeftDiag grid ++ slideRightDiag grid

-----------------------------------------------------------------------------
-- #12
-- Which is the first triangle number to have over five-hundred divisors?

getProperDivisors n = filter (\x -> (rem n x) == 0) [1..(n-1)]

triangleNumbers = [triangleNumber n | n <- [1..]]

triangleNumber n = (n * (n+1)) `quot` 2

euler_p12 =
    head $ filter (\x -> (length $ getProperDivisors x) > 500) triangleNumbers

-- A brute-force factor search
getAllFactors n = 
    let
        test [] = 2
        test (x:xs) =
            if mod n x == 0
            then 1+(test xs)
            else (test xs)
    in
        test [2..(n-1)]

-- too slow!
--euler_p12 =
--    filter (\x -> (getAllFactors x) > 500) triangleNumbers

-----------------------------------------------------------------------------
-- #13

euler_p13 =
    let
        magic :: [Integer]
        magic = 
            [37107287533902102798797998220837590246510135740250,
            46376937677490009712648124896970078050417018260538,
            74324986199524741059474233309513058123726617309629,
            91942213363574161572522430563301811072406154908250,
            23067588207539346171171980310421047513778063246676,
            89261670696623633820136378418383684178734361726757,
            28112879812849979408065481931592621691275889832738,
            44274228917432520321923589422876796487670272189318,
            47451445736001306439091167216856844588711603153276,
            70386486105843025439939619828917593665686757934951,
            62176457141856560629502157223196586755079324193331,
            64906352462741904929101432445813822663347944758178,
            92575867718337217661963751590579239728245598838407,
            58203565325359399008402633568948830189458628227828,
            80181199384826282014278194139940567587151170094390,
            35398664372827112653829987240784473053190104293586,
            86515506006295864861532075273371959191420517255829,
            71693888707715466499115593487603532921714970056938,
            54370070576826684624621495650076471787294438377604,
            53282654108756828443191190634694037855217779295145,
            36123272525000296071075082563815656710885258350721,
            45876576172410976447339110607218265236877223636045,
            17423706905851860660448207621209813287860733969412,
            81142660418086830619328460811191061556940512689692,
            51934325451728388641918047049293215058642563049483,
            62467221648435076201727918039944693004732956340691,
            15732444386908125794514089057706229429197107928209,
            55037687525678773091862540744969844508330393682126,
            18336384825330154686196124348767681297534375946515,
            80386287592878490201521685554828717201219257766954,
            78182833757993103614740356856449095527097864797581,
            16726320100436897842553539920931837441497806860984,
            48403098129077791799088218795327364475675590848030,
            87086987551392711854517078544161852424320693150332,
            59959406895756536782107074926966537676326235447210,
            69793950679652694742597709739166693763042633987085,
            41052684708299085211399427365734116182760315001271,
            65378607361501080857009149939512557028198746004375,
            35829035317434717326932123578154982629742552737307,
            94953759765105305946966067683156574377167401875275,
            88902802571733229619176668713819931811048770190271,
            25267680276078003013678680992525463401061632866526,
            36270218540497705585629946580636237993140746255962,
            24074486908231174977792365466257246923322810917141,
            91430288197103288597806669760892938638285025333403,
            34413065578016127815921815005561868836468420090470,
            23053081172816430487623791969842487255036638784583,
            11487696932154902810424020138335124462181441773470,
            63783299490636259666498587618221225225512486764533,
            67720186971698544312419572409913959008952310058822,
            95548255300263520781532296796249481641953868218774,
            76085327132285723110424803456124867697064507995236,
            37774242535411291684276865538926205024910326572967,
            23701913275725675285653248258265463092207058596522,
            29798860272258331913126375147341994889534765745501,
            18495701454879288984856827726077713721403798879715,
            38298203783031473527721580348144513491373226651381,
            34829543829199918180278916522431027392251122869539,
            40957953066405232632538044100059654939159879593635,
            29746152185502371307642255121183693803580388584903,
            41698116222072977186158236678424689157993532961922,
            62467957194401269043877107275048102390895523597457,
            23189706772547915061505504953922979530901129967519,
            86188088225875314529584099251203829009407770775672,
            11306739708304724483816533873502340845647058077308,
            82959174767140363198008187129011875491310547126581,
            97623331044818386269515456334926366572897563400500,
            42846280183517070527831839425882145521227251250327,
            55121603546981200581762165212827652751691296897789,
            32238195734329339946437501907836945765883352399886,
            75506164965184775180738168837861091527357929701337,
            62177842752192623401942399639168044983993173312731,
            32924185707147349566916674687634660915035914677504,
            99518671430235219628894890102423325116913619626622,
            73267460800591547471830798392868535206946944540724,
            76841822524674417161514036427982273348055556214818,
            97142617910342598647204516893989422179826088076852,
            87783646182799346313767754307809363333018982642090,
            10848802521674670883215120185883543223812876952786,
            71329612474782464538636993009049310363619763878039,
            62184073572399794223406235393808339651327408011116,
            66627891981488087797941876876144230030984490851411,
            60661826293682836764744779239180335110989069790714,
            85786944089552990653640447425576083659976645795096,
            66024396409905389607120198219976047599490197230297,
            64913982680032973156037120041377903785566085089252,
            16730939319872750275468906903707539413042652315011,
            94809377245048795150954100921645863754710598436791,
            78639167021187492431995700641917969777599028300699,
            15368713711936614952811305876380278410754449733078,
            40789923115535562561142322423255033685442488917353,
            44889911501440648020369068063960672322193204149535,
            41503128880339536053299340368006977710650566631954,
            81234880673210146739058568557934581403627822703280,
            82616570773948327592232845941706525094512325230608,
            22918802058777319719839450180888072429661980811197,
            77158542502016545090413245809786882778948721859617,
            72107838435069186155435662884062257473692284509516,
            20849603980134001723930671666823555245252804609722,
            53503534226472524250874054075591789781264330331690]
   in
        take 10 $ show $ sum magic
    
-----------------------------------------------------------------------------
-- #14

p14seq n
    | n == 1 = [n]
    | mod n 2 == 0 = 
        n : (p14seq $ quot n 2)
    | otherwise = 
        n : (p14seq $ (n*3) + 1)

maxfst l =
    let
        findmax [] maxTuple = maxTuple
        findmax ((a,b):xs) maxTuple =
            if a > fst maxTuple
            then findmax xs (a,b)
            else findmax xs maxTuple
    in
        findmax l (0,0)

minP14seq n m =
    let 
        p14seq n' depth
            | depth > m = True
            | n' == 1 = False
            | mod n' 2 == 0 = 
                p14seq (quot n' 2) (depth+1)
            | otherwise = 
                p14seq (quot n' 2) (depth+1)
    in
        minP14seq n 0
    
seeds 0 = []
seeds n = n : (seeds (n-1))

euler_p14 =
    snd $ maxfst [(length $ p14seq n, n) | 
                  n <- filter (\x -> minP14seq x 10) $ seeds 999999]

-----------------------------------------------------------------------------
-- #15
-- How many routes are there through a 20x20 grid?
-- TODO: count the # of unique combinations of 20 down and 20 right arrows

comb n k = quot (fac n) ((fac k)*(fac (n-k)))

centralBinomialCoeff n = comb (2*n) n

countOf [] x = 0
countOf l x 
    | head l == x = 1 + countOf (tail l) x
    | otherwise = countOf (tail l) x

-- I didn't know how to set up the combinatorial at first, so I simulated
-- for smaller N with 0=right-arrow, 1=down-arrow and discovered the 
-- Central Binomial Coefficient that way.

simulate_p15seq n = length $
                filter (\x -> ((countOf x '1') == n) &&
                              ((countOf x '0') == n)) $
                    map (\x -> showBinary x (n*2)) [0..(2^(n*2)-1)]

powersOf2 = [1] ++ [x*2 | x <- powersOf2]

maxPowerOf2in n = head $ reverse $ takeWhile (\x -> x <= n) powersOf2

getPowersOf2in :: Integer -> [Integer]
getPowersOf2in 0 = []
getPowersOf2in n = 
    let 
        currentPower = maxPowerOf2in n
    in
        (currentPower) : (getPowersOf2in (n-currentPower))

showBinary n k =
    let 
        digitPowers = getPowersOf2in n
        allPowers = reverse $ takeWhile (\x -> x <= n || x < 2^k) powersOf2
        showDigits _ [] = []
        showDigits [] (digit:digits) =
            '0' : (showDigits [] digits)
        showDigits (one:ones) (digit:digits) =
            if one == digit
            then '1' : (showDigits ones digits)
            else '0' : (showDigits (one:ones) digits)
    in
        showDigits digitPowers allPowers

euler_p15 = centralBinomialCoeff 20

-----------------------------------------------------------------------------
-- #16
-- What is the sum of the digits of the number 2^1000?

euler_p16 =
    sum [fst $ head $ readDec (x:"") | x <- show (2^1000)]

-----------------------------------------------------------------------------
-- #17

prettyDigit n
    | n == 0 = ""
    | n == 1 = "one"
    | n == 2 = "two"
    | n == 3 = "three"
    | n == 4 = "four"
    | n == 5 = "five"
    | n == 6 = "six"
    | n == 7 = "seven"
    | n == 8 = "eight"
    | n == 9 = "nine"
    | n == 10 = "ten"
    | n == 11 = "eleven"
    | n == 12 = "twelve"
    | n == 13 = "thirteen"
    | n == 14 = "fourteen"
    | n == 15 = "fifteen"
    | n == 16 = "sixteen"
    | n == 17 = "seventeen"
    | n == 18 = "eighteen"
    | n == 19 = "nineteen"
    | n == 20 = "twenty"
    | n == 30 = "thirty"
    | n == 40 = "forty"
    | n == 50 = "fifty"
    | n == 60 = "sixty"
    | n == 70 = "seventy"
    | n == 80 = "eighty"
    | n == 90 = "ninety"
    | n > 99 = prettyDigit (quot n 100) ++ " hundred"
    
prettyNumber n 
    | n == 1000 =
        "one thousand"
    | mod n 100 == 0 = prettyDigit (n - (mod n 100))
    | n > 99 = 
        (prettyDigit (n - (mod n 100))) ++ " and " ++ (prettyNumber $ mod n 100)
    | n > 19 = 
        (prettyDigit (n - (mod n 10))) ++ " " ++ (prettyNumber $ mod n 10)
    | otherwise = prettyDigit n
    
euler_p17 =
    length $ filter (\x -> x /= ' ') $ 
        foldr (++) "" $ map prettyNumber $ [1..1000]
    
-----------------------------------------------------------------------------
-- #18

-- Absolutely hideous first attempt

indexOfMax l = fromJust $ findIndex (\x -> x == maximum l) l

naiveTriangleDive [] _ = []
naiveTriangleDive (top:triangle) lastIndex =
    let
        chooseFrom = take 2 $ snd $ splitAt lastIndex top
    in
        (maximum chooseFrom) : 
            (naiveTriangleDive triangle $ indexOfMax top)

-- binaryDive is a successful, though brute-force, top-down descent

leftTriangle triangle =
    map (reverse.tail.reverse) triangle

rightTriangle triangle =
    map tail triangle

binaryDive :: [[Int]] -> Int
binaryDive ((top:[]):[]) = top
binaryDive ((top:[]):rest) =
    top + 
        (maximum $ [binaryDive $ leftTriangle rest,
                    binaryDive $ rightTriangle rest])

-- bottomUpPathfinder is my non-brute force solution, 
-- it works its way up from the bottom.

bottomUpPathfinder ((top:[]):[]) = top
bottomUpPathfinder triangle =
    let 
        (bottom:next:rest) = reverse triangle
        maximizeBottom bottom next =
            let
                bottomPairs = [[b1,b2] | (b1,b2) <- zip bottom $ tail bottom]
            in
                [n + maximum b | (n,b) <- zip next bottomPairs]
    in
        bottomUpPathfinder $ reverse $
            (maximizeBottom bottom next) :
            rest

euler_p18 =
    let 
        example = [[3],[7,5],[2,4,6],[8,5,9,3]]
        triangle = [
                                [75],
                               [95,64],
                             [17,47,82],
                            [18,35,87,10],
                          [20,04,82,47,65],
                         [19,01,23,75,03,34],
                       [88,02,77,73,07,63,67],
                      [99,65,04,28,06,16,70,92],
                    [41,41,26,56,83,40,80,70,33],
                   [41,48,72,33,47,32,37,16,94,29],
                 [53,71,44,65,25,43,91,52,97,51,14],
                [70,11,33,28,77,73,17,78,39,68,17,57],
              [91,71,52,38,17,14,91,43,58,50,27,29,48],
             [63,66,04,68,89,53,67,30,73,16,69,87,40,31],
           [04,62,98,27,23,09,70,98,73,93,38,53,60,04,23]
         ]
    in
        bottomUpPathfinder triangle
    
-----------------------------------------------------------------------------
-- #20
-- Sum of the digits of 100!

fac n = foldl (*) 1 [1..n]

euler_p20 =
    sum $ map digitToInt $ show $ fac 100
    
-----------------------------------------------------------------------------
-- #21
euler_p21 =
    let
        d n = sum $ getProperDivisors n
        
        findAmicable amiMap 
            | Map.size amiMap == 0 = []
            | otherwise =
                let
                    (a,b) = Map.elemAt 0 amiMap
                in
                    case Map.lookup b amiMap of
                        Just x | x == a && a /= b -> a : b : 
                            (findAmicable $ Map.delete a $ Map.delete b amiMap)
                        _ -> findAmicable $ Map.delete a $ Map.delete b amiMap
    in
        sum $ findAmicable $ Map.fromList $ map (\x -> (x, (d x))) [1..9999]

-----------------------------------------------------------------------------
-- #23
isAbundant n = (sum $ getProperDivisors n) > n
euler_p23 = sum $ filter isAbundant $ filter (not.isPrime) [1..28123]

-----------------------------------------------------------------------------
-- #24
-- What is the millionth lexicographic permutation of the digits 
-- 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
{-
shift :: [a] -> [a]
shift (x:xs) = xs ++ [x]
perm :: [a] -> [[a]]
perm (x:xs) = map (x:) $ lexPerm $ roll xs
lexPerm :: [[a]] -> [[a]]
lexPerm (x:y:z:[]) = [[z,x,y],[z,y,x]]
lexPerm ls = map perm ls
-}

-----------------------------------------------------------------------------
-- #25
-- nth term in fibonacci sequence with >1000 digits?

euler_p25 =
    snd $ head $ 
        filter (\x -> (fst x) > 10^999-1) [(x,y) | (x,y) <- zip fib [1..]]

-----------------------------------------------------------------------------
-- #35

roll l =
    let
        roller l 0 = []
        roller (x:xs) i = (x:xs) : (roller (xs ++ [x]) (i-1))
    in
        roller l $ length l
    
allTrue l = foldl (&&) True l
anyTrue l = foldl (||) False l

isCircularPrime n = 
    allTrue $ map isPrime $ map (fst.head.readDec) $ roll $ show n

hasBadDigits 2 = False
hasBadDigits 5 = False
hasBadDigits n =
    let
        findBadDigits [] = False
        findBadDigits (x:xs) =
            case x of
                '0' -> True
                '2' -> True
                '4' -> True
                '5' -> True
                '6' -> True
                '8' -> True
                otherwise -> findBadDigits xs
    in
        findBadDigits $ show n

fracDigits 0 d = []
fracDigits n d = 
    let 
        q = quot (n*10) d
        r = rem (n*10) d
    in
        if r == n
        then q : (fracDigits 0 d)
        else q : (fracDigits r d)

chaseLoop l =
    let
        chaseLoop' _ _ 1000 = chaseLoop $ tail l
        chaseLoop' l [] n = []
        chaseLoop' l l' n =
            if ((take n l) == (take n $ drop n l)) && 
               ((take n l) == (take n $ drop n l'))
            then take n l
            else chaseLoop' l (tail l') (n+1)
    in
        chaseLoop' l (tail l) 1
    
euler_p26 =
    maximumBy (\x y -> compare (fst x) (fst y)) $
        zip (map (\x -> length $ chaseLoop $ fracDigits 1 x) [1..1000]) [1..1000]
    
-- Using a (brute-force) reduced subset
euler_p35 = length $
    filter isCircularPrime $ filter (not.hasBadDigits) [2..999999]

-----------------------------------------------------------------------------
-- #48
-- Find the last ten digits of 1^1 + 2^2 + ... + 1000^1000.

euler_p48 =
    (sum [x^x | x <- [1..1000]]) `mod` (10^10)
    
-----------------------------------------------------------------------------
-- #67
-- using new bottomUpPathFinder algo

euler_p67 = do
    contents <- readFile "data/triangle.txt"
    putStrLn $ show $
        bottomUpPathfinder $ 
        map (\x -> map (fst.head.readDec) $ words x) $ lines contents

-----------------------------------------------------------------------------
-- # 80

sqrtDigits n =
    let
        findY p c x = ((20*p)+x)*x
        findX p c x =
            let
                y = findY p c x
            in
                case x of
                    x' | (findY p c (x'+1) > c) && y <= c -> (x', y)
                       | y > c -> findX p c (x'-1)
                       | otherwise -> findX p c (x'+1)
        guessX p c
            | p == 0 = c
            | otherwise = quot c (20*p)
        sqrtDigits' p [] 0 = []
        sqrtDigits' p [] r = sqrtDigits' p [0] r
        sqrtDigits' p (d:ds) r =
            let
                c = (r*100)+d
                (x,y) = findX p c (guessX p c)
            in
                x : sqrtDigits' ((p*10)+x) ds (c-y)
    in
        sqrtDigits' 0 [n] 0

euler_p80 = 
    let
        -- Dirty but correct for this problem
        isIrrationalSqrt n = (length $ take 100 $ sqrtDigits n) == 100
    in
        sum $ map (\x -> sum $ take 100 $ sqrtDigits x) $ 
            filter isIrrationalSqrt [2..100]
    
-----------------------------------------------------------------------------
-- #92
isSqChain89 1 = False
isSqChain89 7 = False
isSqChain89 10 = False
isSqChain89 13 = False
isSqChain89 19 = False
isSqChain89 23 = False
isSqChain89 28 = False
isSqChain89 31 = False
isSqChain89 32 = False
isSqChain89 44 = False
isSqChain89 49 = False
isSqChain89 68 = False
isSqChain89 70 = False
isSqChain89 79 = False
isSqChain89 82 = False
isSqChain89 86 = False
isSqChain89 91 = False
isSqChain89 94 = False
isSqChain89 97 = False
isSqChain89 100 = False
isSqChain89 n
    | n < 100 = True
    | otherwise = isSqChain89 $ sum $ getSqDigits n

digits n = map digitToInt $ show n

getSqDigits n = map (\x -> x*x) $ digits n

getSqChain89 n
    | (n == 1) || (n == 89) = [n]
    | otherwise = n : (getSqChain89 $ sum $ getSqDigits n)

sumDigits n =
    sum $ digits n

euler_p92 = 
    length $ filter isSqChain89 [2..9999999]

-----------------------------------------------------------------------------
-- #97
    
euler_p97 = mod (28433 * 2^7830457 + 1) 10000000000

-----------------------------------------------------------------------------
-- #112

isIncrDigits n = allTrue $ map (\(x,y) -> x<=y) $
    zip (digits n) (tail $ digits n)
isDecrDigits n = allTrue $ map (\(x,y) -> x>=y) $
    zip (digits n) (tail $ digits n)

isBouncy n = ((not.isIncrDigits) n) && ((not.isDecrDigits) n)

euler_p112 =
    let
        pctLimit = 99
        bouncy :: Int -> Int -> Int
        bouncy n b
            | (truncate ((fromIntegral b)/(fromIntegral (n-1))*100.0)) >= pctLimit = (n-1)
            | isBouncy n = bouncy (n+1) (b+1)
            | otherwise = bouncy (n+1) b
    in
        bouncy 0 0

-----------------------------------------------------------------------------
-- #149
lagFibSeed n = 
    (mod (100003 - 200003*n + 300007*(n^3)) 1000000) - 500000

lagFib = 
    [lagFibSeed x | x <- [1..55]] ++
        [(mod (x + y + 1000000) 1000000) - 500000 |
            (x,y) <- zip (drop 31 lagFib) lagFib]

-----------------------------------------------------------------------------
-- #160
-- The last five digits before the trailing zeroes in 10^12!.
euler_p160 =
    show $ fac (10^12) -- This is too big!
    
